|
In combinatorics, a Helly family of order ''k'' is a family of sets such that any minimal subfamily with an empty intersection has ''k'' or fewer sets in it. Equivalently, every finite subfamily such that every -fold intersection is non-empty has non-empty total intersection.〔.〕 The ''k''-Helly property is the property of being a Helly family of order ''k''.〔. See in particular Section 2.5, "Helly Property", (pp. 393–394 ).〕 These concepts are named after Eduard Helly (1884 - 1943); Helly's theorem on convex sets, which gave rise to this notion, states that convex sets in Euclidean space of dimension ''n'' are a Helly family of order ''n'' + 1.〔 The number ''k'' is frequently omitted from these names in the case that ''k'' = 2. == Examples == * In the family of all subsets of the set , the subfamily has an empty intersection, but removing any set from this subfamily causes it to have a nonempty intersection. Therefore, it is a minimal subfamily with an empty intersection. It has four sets in it, and is the largest possible minimal subfamily with an empty intersection, so the family of all subsets of the set is a Helly family of order 4. * Let I be a finite set of closed intervals of the real line with an empty intersection. Let A be the interval whose left endpoint ''a'' is as large as possible, and let B be the interval whose right endpoint ''b'' is as small as possible. Then, if ''a'' were less than or equal to ''b'', all numbers in the range () would belong to all invervals of I, violating the assumption that the intersection of I is empty, so it must be the case that ''a'' > ''b''. Thus, the two-interval subfamily has an empty intersection, and the family I cannot be minimal unless I = . Therefore, all minimal families of intervals with empty intersections have two or fewer intervals in them, showing that the set of all intervals is a Helly family of order 2.〔This is the one-dimensional case of Helly's theorem. For essentially this proof, with a colorful phrasing involving sleeping students, see .〕 * The family of infinite arithmetic progressions of integers also has the 2-Helly property. That is, whenever a finite collection of progressions has the property that no two of them are disjoint, then there exists an integer that belongs to all of them; this is the Chinese remainder theorem.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Helly family」の詳細全文を読む スポンサード リンク
|